package Tree;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-30  20:13
 * @Description: TODO
 * @Version: 1.0
 */
public class 二叉搜索树中第K小的元素230 {

    int res, k;
    // 采用的中序遍历 左中右

    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            // 一直遍历的左
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 然后开始弹出
            root = stack.pop();
            --k;
            if (k == 0) {
                break;
            }
            // 然后使用右边
            root = root.right;
        }
        return root.val;
    }

    void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        // 左
        dfs(root.left);
        // 中
        if (k == 0) {
            return;
        }
        if (--k == 0) {
            res = root.val;
        }
        // 右
        dfs(root.right);
    }

    public int kthSmallest2(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
